package Demo01;

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改


import java.math.BigInteger;

class c<K,V> {
    K key;
    V value;

    public c(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

class Factorial {
    public static void main5(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        //数组长度
        int n = scan.nextInt();
        int[] arr = new int[n];
        int m = scan.nextInt();
        int[][] lArr = new int[m][2];
        //统计频率
        PriorityQueue<c<Integer,Integer>> p = new PriorityQueue<>(new Comparator<c<Integer, Integer>>() {
            @Override
            public int compare(c<Integer, Integer> o1, c<Integer, Integer> o2) {
                return o1.key - o2.value;
            }
        });
        //获得查询
        for (int i = 0;i < m;i++) {
            int l = scan.nextInt();
            int r = scan.nextInt();
            for(int j = l-1 ; j<=r-1;j++) {

            }
        }

        scan.close();
    }
    public static void main4(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        //部落数
        int n = scan.nextInt();
        PriorityQueue<Integer> p = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            p.add(scan.nextInt());
        }
        int priceSum = 0;
        while (p.size()>1) {
            int p1 = p.poll();
            int p2 = p.poll();
            int sum = p1 + p2;
            priceSum += sum*2;
            p.add(sum);
        }

        scan.close();
    }
    public static void main3(String[] args) {
        int n = 100; // 示例：计算 100!
        BigInteger factorial = calculateFactorial(n);
        System.out.println("Factorial of " + n + " is: " + factorial);
    }

    public static BigInteger calculateFactorial(int n) {
        if (n == 0) {
            return BigInteger.ONE;
        }
        return BigInteger.valueOf(n).multiply(calculateFactorial(n - 1));
    }
}

public class Main {
    public static void main(String[] args) {

    }
    public static void main2(String[] args) {
        char[] arr = new char[10];
        Arrays.fill(arr, '0');
        arr[0] = '1';
        int out = 0;
        for (int i = 2; i <= 10000; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                int tmp = arr[j] - '0' + out;
                tmp *= i;
                int in = tmp % 10;
                arr[j] = (char) (in + '0');
                out = tmp / 10;
            }
        }
    }

    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        //数量
        int N = scan.nextInt();
        //操作次数
        int Q = scan.nextInt();
        //初始化数组
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scan.nextInt();
        }
        //差分数组
        int[] diff = new int[N + 1];
        for (int i = 0; i <= Q - 1; i++) {
            //一次操作
            int l = scan.nextInt() - 1;
            int r = scan.nextInt() - 1;
            int x = scan.nextInt();
            diff[l] += x;
            diff[r + 1] -= x;
        }
        for (int i = 1; i <= N - 1; i++) {
            diff[i] += diff[i - 1];
        }
        for (int i = 0; i <= N - 1; i++) {
            arr[i] += diff[i];
            if (arr[i] < 0) {
                System.out.print(0 + " ");
            } else {
                System.out.print(arr[i] + " ");
            }
        }

        scan.close();
    }
}

/*public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int l = scan.nextInt();
        int count = scan.nextInt();
        scan.close();
    }
}*/

// 1:无需package
// 2: 类名必须Main, 不可修改

/*public class Main {
    public static void main(String[] args) {
        //在此输入您的代码...
        String s = "2021ABCD";
        long sum = 0;
        for (int i = s.length() - 1, k = 0; i >= 0 ; i-- ,k++ ) {
            char c = s.charAt(i);
            if (c>='A'&&c<='D') {
                sum += Math.pow(16,k)*(c-'A'+10);
            }
            if (c>='0'&&c<='9') {
                sum += Math.pow(16,k)*(c-'0');
            }
        }
        System .out.print(sum);
    }
}*/
/*public class Main {

    public static void main(String[] args) {
        int[] arr = {0,0,0,0};
        Solution solution = new Solution();
        System.out.println(solution.threeSum(arr));

    }
}*/

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();

        Arrays.sort(nums);
        int l = nums.length;
        for (int i = l - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                } else if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else {
                    List<Integer> listT = new ArrayList<>();
                    listT.add(nums[i]);
                    listT.add(nums[left]);
                    listT.add(nums[right]);
                    left++;
                    right--;
                }
            }
        }

        return list;
    }

    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        int l = nums.length;
        for (int i = l - 1; i >= 2; i--) {
            //从后往前固定最大值
            //对中间值进行判断
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return count;
    }

    public int[] twoSum(int[] price, int target) {
        int[] arr = new int[2];
        int l = price.length;
        int left = 0;
        int right = l - 1;
        while (left < right) {
            if (price[left] + price[right] > target) {
                right--;
            } else if (price[left] + price[right] < target) {
                left++;
            } else {
                arr[0] = price[left];
                arr[1] = price[right];
                break;
            }
        }

        return arr;
    }
}